package 中等.搜索.深度优先搜索;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元
 * 格可以是一艘战舰 'X' 或者是一个空位 '.' ，返回在甲板 board 上放
 * 置的 战舰 的数量。
 * <p>
 * 战舰 只能水平或者垂直放置在 board 上。换句话说，战舰只能按 1 x k
 * （1 行，k 列）或 k x 1（k 行，1 列）的形状建造，其中 k 可以是任意
 * 大小。两艘战舰之间至少有一个水平或垂直的空位分隔 （即没有相邻的战舰）。
 * <p>
 * 进阶：你可以实现一次扫描算法，并只使用 O(1) 额外空间，并且不修改
 * board 的值来解决这个问题吗？
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/battleships-in-a-board
 */
public class 甲板上的战舰_419 {

    public static void main(String[] args) {

        char[][] board = {{'X', '.', '.', 'X'}, {'.', '.', '.', 'X'}, {'.', '.', '.', 'X'}};
        char[][] board2 = {{'X', 'X', 'X'}};
        System.out.println(efficientCountBattleships(board));

    }

    /**
     * 深度搜索+栈，缺点，改变了原数组，
     * 如果建一个数组来记录走过的地方，那么空间复杂度会变成O(i*j)
     *
     * @param board
     * @return
     */
    public static int countBattleships(char[][] board) {
        int count = 0;
        int rows = board.length;
        int columns = board[0].length;
        //定义两个方向，向下或者向右
        int[][] direction = new int[][]{{1, 0}, {0, 1}};
        //遍历甲板
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if ('X' == board[i][j]) {   //如果遍历到战舰
                    count++;
                    board[i][j] = '.';
                    Deque<int[]> stack = new ArrayDeque<>();
                    stack.addFirst(new int[]{i, j});
                    while (!stack.isEmpty()) {
                        int[] curBattle = stack.pollFirst();
                        for (int[] direct : direction) {
                            int row = curBattle[0] + direct[0];
                            int column = curBattle[1] + direct[1];
                            if (row < rows && row >= 0 && column < columns && column >= 0) {
                                if ('X' == board[row][column]) {
                                    board[row][column] = '.';
                                    stack.addFirst(new int[]{row, column});
                                }
                            }

                        }
                    }
                }
            }
        }
        return count;
    }

    /**
     * 因为战舰只能存在某一行或者某一列
     * 不使用栈直接用遍历实现
     *
     * @param board
     * @return
     */
    public static int countBattleships2(char[][] board) {
        int count = 0;
        int rows = board.length;
        int columns = board[0].length;
        //遍历甲板
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                //如果遍历到战舰
                if (board[i][j] == 'X') {
                    count++;
                    board[i][j] = '.';
                    for (int i1 = i + 1; i1 < rows && board[i1][j] == 'X'; i1++) {  //将下方相邻的战舰全部排除
                        board[i1][j] = '.';
                    }
                    for (int j1 = j + 1; j1 < columns && board[i][j1] == 'X'; j1++) { //将右方相邻的战舰全部排除
                        board[i][j1] = '.';
                    }
                }
            }
        }
        return count;
    }

    /**
     * 如果不想改变原来的数组，通过观察，可以一个战舰
     * 只统计它的最左边或者最上面的'X'
     * <p>
     * 战舰最左边的X必须满足的条件：
     * 上方的空间必须为'.'，或者越出边界
     * 其左边必须为'.'，或者越出边界
     *
     * @param board
     * @return
     */
    public static int efficientCountBattleships(char[][] board) {
        int count = 0;
        int rows = board.length;
        int columns = board[0].length;
        //遍历甲板
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (board[i][j] == 'X') {
                    if ((i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')) {
                        count++;

                    }
                }
            }
        }
        return count;
    }

}
